<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>trie</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="trie">trie</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=AXjmTQ8LEoI&amp;list=PLrmLmBdmIlpuE5GEMDXWf0PWbBD9Ga1lO&amp;index=4">https://www.youtube.com/watch?v=AXjmTQ8LEoI&amp;list=PLrmLmBdmIlpuE5GEMDXWf0PWbBD9Ga1lO&amp;index=4</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/suffixprefix/Trie.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/suffixprefix/Trie.java</a></li>
</ul>
<p>前缀树的插入，查找，删除</p>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.suffixprefix;

<span class="hljs-keyword">import</span> java.util.HashMap;
<span class="hljs-keyword">import</span> java.util.Map;

<span class="hljs-comment">/**
 * Date 04/25/2016
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Insert/delete/search into trie data structure
 *
 * Reference
 * https://en.wikipedia.org/wiki/Trie
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span> </span>{

    <span class="hljs-keyword">private</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TrieNode</span> </span>{
        Map&lt;Character, TrieNode&gt; children;
        <span class="hljs-keyword">boolean</span> endOfWord;
        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">TrieNode</span><span class="hljs-params">()</span> </span>{
            children = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();
            endOfWord = <span class="hljs-keyword">false</span>;
        }
    }

    <span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> TrieNode root;
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Trie</span><span class="hljs-params">()</span> </span>{
        root = <span class="hljs-keyword">new</span> TrieNode();
    }

    <span class="hljs-comment">/**
     * Iterative implementation of insert into trie
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(String word)</span> </span>{
        TrieNode current = root;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; word.length(); i++) {
            <span class="hljs-keyword">char</span> ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) {
                node = <span class="hljs-keyword">new</span> TrieNode();
                current.children.put(ch, node);
            }
            current = node;
        }
        <span class="hljs-comment">//mark the current nodes endOfWord as true</span>
        current.endOfWord = <span class="hljs-keyword">true</span>;
    }

    <span class="hljs-comment">/**
     * Recursive implementation of insert into trie
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertRecursive</span><span class="hljs-params">(String word)</span> </span>{
        insertRecursive(root, word, <span class="hljs-number">0</span>);
    }


    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertRecursive</span><span class="hljs-params">(TrieNode current, String word, <span class="hljs-keyword">int</span> index)</span> </span>{
        <span class="hljs-keyword">if</span> (index == word.length()) {
            <span class="hljs-comment">//if end of word is reached then mark endOfWord as true on current node</span>
            current.endOfWord = <span class="hljs-keyword">true</span>;
            <span class="hljs-keyword">return</span>;
        }
        <span class="hljs-keyword">char</span> ch = word.charAt(index);
        TrieNode node = current.children.get(ch);

        <span class="hljs-comment">//if node does not exists in map then create one and put it into map</span>
        <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) {
            node = <span class="hljs-keyword">new</span> TrieNode();
            current.children.put(ch, node);
        }
        insertRecursive(node, word, index + <span class="hljs-number">1</span>);
    }

    <span class="hljs-comment">/**
     * Iterative implementation of search into trie.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">search</span><span class="hljs-params">(String word)</span> </span>{
        TrieNode current = root;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; word.length(); i++) {
            <span class="hljs-keyword">char</span> ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            <span class="hljs-comment">//if node does not exist for given char then return false</span>
            <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) {
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
            }
            current = node;
        }
        <span class="hljs-comment">//return true of current's endOfWord is true else return false.</span>
        <span class="hljs-keyword">return</span> current.endOfWord;
    }

    <span class="hljs-comment">/**
     * Recursive implementation of search into trie.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">searchRecursive</span><span class="hljs-params">(String word)</span> </span>{
        <span class="hljs-keyword">return</span> searchRecursive(root, word, <span class="hljs-number">0</span>);
    }
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">searchRecursive</span><span class="hljs-params">(TrieNode current, String word, <span class="hljs-keyword">int</span> index)</span> </span>{
        <span class="hljs-keyword">if</span> (index == word.length()) {
            <span class="hljs-comment">//return true of current's endOfWord is true else return false.</span>
            <span class="hljs-keyword">return</span> current.endOfWord;
        }
        <span class="hljs-keyword">char</span> ch = word.charAt(index);
        TrieNode node = current.children.get(ch);
        <span class="hljs-comment">//if node does not exist for given char then return false</span>
        <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
        }
        <span class="hljs-keyword">return</span> searchRecursive(node, word, index + <span class="hljs-number">1</span>);
    }

    <span class="hljs-comment">/**
     * Delete word from trie.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">delete</span><span class="hljs-params">(String word)</span> </span>{
        delete(root, word, <span class="hljs-number">0</span>);
    }

    <span class="hljs-comment">/**
     * Returns true if parent should delete the mapping
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">delete</span><span class="hljs-params">(TrieNode current, String word, <span class="hljs-keyword">int</span> index)</span> </span>{
        <span class="hljs-keyword">if</span> (index == word.length()) {
            <span class="hljs-comment">//when end of word is reached only delete if currrent.endOfWord is true.</span>
            <span class="hljs-keyword">if</span> (!current.endOfWord) {
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
            }
            current.endOfWord = <span class="hljs-keyword">false</span>;
            <span class="hljs-comment">//if current has no other mapping then return true</span>
            <span class="hljs-keyword">return</span> current.children.size() == <span class="hljs-number">0</span>;
        }
        <span class="hljs-keyword">char</span> ch = word.charAt(index);
        TrieNode node = current.children.get(ch);
        <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
        }
        <span class="hljs-keyword">boolean</span> shouldDeleteCurrentNode = delete(node, word, index + <span class="hljs-number">1</span>);

        <span class="hljs-comment">//if true is returned then delete the mapping of character and trienode reference from map.</span>
        <span class="hljs-keyword">if</span> (shouldDeleteCurrentNode) {
            current.children.remove(ch);
            <span class="hljs-comment">//return true if no mappings are left in the map.</span>
            <span class="hljs-keyword">return</span> current.children.size() == <span class="hljs-number">0</span>;
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    }
}
</div></code></pre>
<p>我的版本，也不知道对不对</p>
<pre><code class="language-python"><div><span class="hljs-comment"># coding:utf-8</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span><span class="hljs-params">(object)</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.children = {}
        self.end = <span class="hljs-literal">False</span>


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">create</span><span class="hljs-params">(words)</span>:</span>
    root = Node()
    <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words:
        update(root, word)
    <span class="hljs-keyword">return</span> root

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">update</span><span class="hljs-params">(node, word)</span>:</span>
    <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> word:
        <span class="hljs-keyword">if</span> c <span class="hljs-keyword">in</span> node.children:
            node = node.children[c]
        <span class="hljs-keyword">else</span>:
            node.children[c] = Node()
            node = node.children[c]
    node.end = <span class="hljs-literal">True</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(node, word)</span>:</span>
    <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> word:
        <span class="hljs-keyword">if</span> c <span class="hljs-keyword">in</span> node.children:
            node = node.children[c]
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>, <span class="hljs-literal">False</span>
    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>, node.end

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">delete</span><span class="hljs-params">(node, word)</span>:</span>
    <span class="hljs-keyword">if</span> word == <span class="hljs-string">""</span>:
        <span class="hljs-keyword">return</span> len(node.children) == <span class="hljs-number">0</span>
    child = node.children[word[<span class="hljs-number">0</span>]]
    child_should_delete = delete(child, word[<span class="hljs-number">1</span>:])
    <span class="hljs-keyword">if</span> len(child.children) == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> child_should_delete == <span class="hljs-literal">True</span>:
        <span class="hljs-keyword">del</span> node.children[word[<span class="hljs-number">0</span>]]
    <span class="hljs-keyword">return</span> len(node.children) == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> node.end == <span class="hljs-literal">False</span>




<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>:</span>
    words = [<span class="hljs-string">"a"</span>, <span class="hljs-string">"abc"</span>, <span class="hljs-string">"abe"</span>,  <span class="hljs-string">"bc"</span>]
    root = create(words)
    words2 = [<span class="hljs-string">"a"</span>, <span class="hljs-string">"ab"</span>, <span class="hljs-string">"abc"</span>, <span class="hljs-string">"b"</span>, <span class="hljs-string">"bc"</span>, <span class="hljs-string">"bd"</span>]
    <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> words2:
        r, f = search(root, w)
        print(<span class="hljs-string">f"w=<span class="hljs-subst">{w}</span> r=<span class="hljs-subst">{r}</span> f=<span class="hljs-subst">{f}</span>"</span>)

    delete(root, <span class="hljs-string">"abc"</span>)
    print(<span class="hljs-string">"after delete ----"</span>)
    words2 = [<span class="hljs-string">"a"</span>, <span class="hljs-string">"ab"</span>, <span class="hljs-string">"abc"</span>, <span class="hljs-string">"b"</span>, <span class="hljs-string">"bc"</span>, <span class="hljs-string">"bd"</span>]
    <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> words2:
        r, f = search(root, w)
        print(<span class="hljs-string">f"w=<span class="hljs-subst">{w}</span> r=<span class="hljs-subst">{r}</span> f=<span class="hljs-subst">{f}</span>"</span>)



<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">'__main__'</span>:
    main()


</div></code></pre>

    </body>
    </html>